package demo.practice.trie;

import java.util.HashMap;
import java.util.Map;

class XorTrie {
    Map<Integer, XorTrie> child = new HashMap<>();
    public int size=0;

    //public boolean isEnd;

    public void insert(int num) {
        XorTrie cur = this;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (cur.child.get(bit) == null) {
                cur.child.put(bit, new XorTrie());
                cur = cur.child.get(bit);
            } else {
                cur = cur.child.get(bit);
            }
        }
        size++;
        //cur.isEnd=true;
    }

    public void insert(int[] nums) {
        for (int num : nums) {
            insert(num);
        }
    }


    public int XorMax(int num) {
        XorTrie cur = this;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (cur.child.get(1) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(1);
                } else {
                    cur = cur.child.get(0);
                }
            } else {
                if (cur.child.get(0) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(0);
                } else {
                    cur = cur.child.get(1);
                }
            }
        }
        return res;
    }

    public int XorMax(int[] nums) {
        int max = 0;
        for (int num : nums) {
            System.out.println(XorMax(num));
            max = Math.max(XorMax(num), max);
        }
        return max;
    }
}